#include <stdlib.h>

static const digit_table[] = {
	1,	
	10,
	100,
	1000,
	10000,
	100000,
	1000000,
	10000000,
	100000000,
	1000000000
};

struct bucket_slist_{
	int data;
	struct bucket_slist_ *next,*prve;
};

static inline void init_bucket(struct bucket_slist_ ** bucket)
{
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		bucket[i] = malloc(sizeof(struct bucket_slist_));
		bucket[i]->next = bucket[i];
		bucket[i]->prve = bucket[i];
	}
}


static inline void add_tail(struct bucket_slist_ **bucket, int data, int radix)
{
	struct bucket_slist_ *new = malloc(sizeof(struct bucket_slist_));
	new->data = data;

	struct bucket_slist_ *p = bucket[radix];
	
	new->next = p;
	new->prve = p->prve;
	p->prve->next = new;
	p->prve = new;
}

static inline void write_back(struct bucket_slist_ **bucket,int *data)
{
	struct bucket_slist_ *p = NULL;

	int i = 0;
	for (i = 0; i < 10; i++)
	{
		p = bucket[i]->next;
		while ( bucket[i]->next != bucket[i] )
		{
			*data++ = p->data;
			bucket[i]->next = p->next;
			p->next->prve = bucket[i];

			free(p);
			p = bucket[i]->next;

		}
	}
}

static inline int get_max_num(int *data, int data_lenth)
{
	int i = 0;
	int max = 0;
	for (i = 0; i < data_lenth; i++)
	{
		if (data[i] > max)
		{
			max = data[i];
		}
	}
	return max;
}
static inline int get_digit(int data)
{
	int digit = 0;
	while (data /= 10)
	{
		digit++;
	}
	digit++;
	return digit;
}
static inline int get_radix(int data, int digit)
{
	return (data / digit_table[digit]) % 10; 
}

int radix_linklist_sort(int *data, int data_lenth)
{
	if (data == 0 || data_lenth <= 0)
	{
		return -1;
	}
	int i = 0, j = 0;
	int digit = 0;
	int is_end = 0;
	int radix = 0;
	int temp = 0;
	int max_digit = 0;

	struct bucket_slist_ * bucket[10];
	init_bucket(bucket);
	
	max_digit = get_digit(get_max_num(data, data_lenth));

	for (i = 0; i < max_digit; i++)
	{
		for (j = 0; j < data_lenth; j++)
		{
			add_tail(bucket, data[j], get_radix(data[j], i));
		}
		write_back(bucket, data);
	}




}
